--[[

This is the constructor for dynamic 
programs that depend only on one 
argument.  It constructs a memo table, 
and then it applies the given operator 
o to cache entries in the memo table 
when they are not yet present.  Repeated 
calls for the same argument retrieve the 
cached value directly from the memo table.  



--]]

function recursively_memoize_oper(o) 
   local memo_table = {} 
   local function fn(arg) 
      local cached = memo_table[arg] 
      if cached then return cached 
      else 
	 local new_val = o(arg,fn) 
	 memo_table[arg] = new_val 
	 return new_val
      end 
   end
   return fn
end

--[[


Given a sequence s, return an 
operator that takes as its arguments 
an integer i and an "approximation" g
to the recursive calls for the optimal value.  

Look in dynamic.lua in this directory, 
at the definition of weighted_interval_sched,
for an example of how to write a function 
that returns an operator.  

--]]

--[[

*Here* fill in a blank to define the recurrence relation 
that your operator will have.  Use the instances in CLRS 
as a guide for what this should be like.  

--]]

function mnas_oper(s) 
   local function f(i,g) 

-- Fill in this blank.  

   return f 
end 

function mnas_max(s) 
   return recursively_memoize_oper(mnas_oper(s))(#s)
end 

--[[

The previous function computes the largest 
sum that a non-adjacent subsequence can achieve.
Now write a function that will print out a 
subsequence that will achieve this maximum.  

You can do this with the same operator mnas_oper, 
by using the idea on p 396 in the CLRS textbook.  
You will also find examples in the solution-printing 
routines in dynamic.lua and dynamic_lcs.lua.  

Here, you want to construct and return a Lua 
array that contains the entries you selected for the 
maximum.  

--]]

function mnas_seq(s) 
   local f = recursively_memoize_oper(mnas_oper(s))

-- Fill in this blank.  

end 


s1 = {3,5,3,7,8,2,1,5,6}
s2 = {3,5,3,8,7,12,1,5,12}
s3 = {3,5,3,8,7,2,1,5,6,3,5,7,8,6}
s3 = {3,5,3,8,7,2,1,5,6,3,5,7,8,6}
s4 = {3,5,3,8,7,2,1,5,6,50,3,7,100}

function mnas_max_make_table_iter(s) 

-- for extra credit, fill in this blank with an 
-- iterative, left-to-right implementation of 
-- the same algorithm.  

-- It should return the table of memoized values.  

end 

function mnas_max_seq_iter(s) 
   local memo_table = mnas_max_make_table_iter(s)

-- for more extra credit, fill in this blank too.
-- it should use the information in the memo table 
-- to reconstruct the value of the maximal non-adjacent 
-- subsequence of s.  

end 

   
      